With computer work stations providing ever more sophisticated graphics, many applications are progressing from rendering wire frame images of objects to rendering shaded images of the surfaces of the objects. While smooth shading provides increased realism and the ability to visualize more complex models, some of the advantages of the wire frame representation may be lost. To benefit from the best of both methods, work station applications often combine wire frame and shaded primitives in the same image, by displaying the shaded surface followed by displaying the edges of the shaded surface to represent the wire frame.
A wire frame can overlay a shaded surface to provide structural information, such as the original data points that generated the model. When a model is constructed using splines, the wire frame can show spline patch boundaries, or the control points used to calculate the spline surface. Another benefit of wire frame modeling is selective highlighting of a subset of the model, such as a subassembly within a complex mechanical part. This information provides insight which can be invaluable to designers.
Applications use a variety of methods to simultaneously display wire frame and shaded objects. Some graphics libraries provide polygon edging support directly, which means a polygon can be rendered with a solid fill and edged in a distinct color with a single call to the library. If no such support exists, the application must display a filled polygon followed by vectors which make up the polygon edge. Some applications prefer to display edge vectors after rendering all polygons, to progressively highlight different features of the model. To correctly combine object primitives with their edges, hidden surface removal must be enabled.
Hidden surface removal is often implemented through a mechanism called a z-buffer. The pixels on a graphics screen are referenced using x and y locations, in the same manner points on a graph are referenced. This is effective, since a graphics screen is two dimensional, so only x and y dimensions are needed. For hidden surface removal, however, the depth of each object being displayed, with respect to the position of the viewer, is needed. Since the depth dimension in a three dimensional coordinate system is typically called the z-dimension, the depth information for hidden surface removal is kept in an area called a z-buffer, which may be located in computer memory or within the graphics display device. The z-buffer contains the depth of each pixel relative to the surface of the screen, and therefore away from the position of the viewer. Thus, when a pixel is to be displayed, its depth location is compared to the depth of the pixel already being displayed on the screen, and if the new pixel is closer to the viewer's position, the new pixel replaces the pixel currently being displayed on the screen. If, however, the new pixel is further away, it is discarded since it would be located behind the pixel currently being displayed.
When converting an object from internal representation to a displayable format, called scan conversion, artifacts can be produced during the combined rendering of a polygonal surface and associated edge vectors. Because the z-buffer values, computed during the scan conversion process, for the surface and the edge vectors may differ slightly, interference between the surface and edge can occur. When edge pixels are overwritten by the surface fill, the resulting polygon edge will have missing pixels. This problem is referred to as edge stitching, since the result looks like sewing stitches. A similar problem occurs when highlighting vectors are sent after the polygonal model is complete. If the edging method leaves interfering values from the polygon fill in the z-buffer, then highlighting vectors will again conflict to produce edge stitching.
The reason the scan conversion process produces these inaccuracies is that scan conversion is really a process of sampling, with all of the associated numerical inaccuracies. If the calculation of z-buffer values is not exactly identical for vectors and polygons, then polygon edging will exhibit artifacts.
One solution to the z-buffer intersection problem is to "pull" the polygon edge z-buffer values forward towards the viewer by arbitrarily changing the z-buffer values for the edges. While this technique can be made to work for simple models, it has serious drawbacks as a general solution. One difficulty with this approach is determining the amount of z-buffer adjustment. If too much correction is applied, polygon edges will poke out into other objects in the scene. If not enough adjustment is made, polygon edges will still exhibit missing pixels. When the magnitude of the adjustment is computed based on the entire z-buffer range, objects which use only a small part of the z-buffer range may be adjusted too much. However, computing the z-buffer adjustment on a per primitive basis adds unacceptable overhead to the polygon edging method.
One prior art method that solves a similar problem is disclosed in "The Hidden Charms of Z-Buffer", Kurt Akeley, in Iris Universe, Volume 11, pages 31-37 (spring 1990). This method is for drawing a decal on a surface, not for drawing edges, however, the process is similar. A decal is a graphic that is placed on the surface of another graphic, such as by painting a symbol on a surface, and thus the two graphics are nearly co-planar. The Akeley decaling method requires three passes and is based on drawing the decal before replacing the z-buffer values for the polygon fill, which prevents the polygon fill from interfering with the decal. The method first renders the polygon fill to the frame buffer while performing z-buffer compares, but without storing new z-buffer values. The second pass renders the decal to the frame buffer while also performing z-buffer compares, but without updating the z-buffer. In the third pass, the method re-renders the polygon fill while performing z-buffer compares, only for the purpose of locating the fill pixels. After locating each fill pixel, the method updates the z-buffer values of each fill pixel without changing the frame buffer. In this method, z-buffer comparisons between the two primitives are avoided since the z-buffer is not updated until after the decal is drawn. This method leaves only the values for the fill pixels in the z-buffer, which is a drawback, since primitives rendered later on top of the decal may still miss pixels. That is, the method works fine initially, but if the decal is redrawn, for example, in a different color, stitching may result since the z-buffer values may be incorrect at the decal locations.
This method also is limited when a portion of the decal extends outside the edge of the polygon. In this instance, the method will render the graphic incorrectly, since the method will not update the z-buffer values for those portions of the decal that are located outside the boundaries of the polygon.
This also limits the method for edging, since some pixels of edges are often located just outside the boundaries of the polygon, as will be shown below with respect to FIG. 2. Even for those edge pixels that lie within the fill boundary, however, some z-buffer values may be incorrect in the Akeley method, as also will be shown below with respect to FIG. 2.
Another prior art method used by the Hewlett Packard Company, called decal edging, adapts the Akeley method by updating the z-buffer during the second pass. Although this method is more likely than the Akeley method to leave correct values in the z-buffer, the method may leave incorrect values in the z-buffer after the third pass. This is because the z-buffer value for fill pixels, updated during the third pass, may replace the z-buffer value for edge pixels, which were updated in the second pass, depending upon how the two z-buffer values compare. Thus, the edge pixels that fall within the fill boundary may have fill pixel z-buffer values after the third pass, which can result in stitching.
There is need in the art, then, for a method for rendering objects and rendering the edges of the objects in a manner that prevents stitching within the edges. A further need in the art is for such a method that renders the edges while leaving the z-buffer values correct for the edges, such that the edges can be rendered subsequent times without leaving artifacts.